其他_611有效三角形的个数.md

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:
输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

示例 2:
输入: nums = [4,2,3,4]
输出: 4

• 方法一： 暴力

var triangleNumber = function(nums) {
  let res = 0;
  for(let i = 0;i<nums.length;i++){
    for(let j = i+1;j<nums.length;j++){
      for(let k = j+1;k<nums.length;k++){
        let max = Math.max(nums[i],nums[j],nums[k])
        let min = Math.min(nums[i],nums[j],nums[k])
        let mid = nums[i]+nums[j]+nums[k]- max - min
        if(max<min+mid){
          res++;
        }
      }
    }
  }

  return res;
};

• 方法二： 暴力+优化

var triangleNumber = function(nums) {
  let res = 0;
  nums = nums.sort((a,b)=>a-b)
  for(let i = 0;i<nums.length;i++){
    for(let j = i+1;j<nums.length;j++){
      for(let k = j+1;k<nums.length;k++){
        if(nums[i]+nums[j]>nums[k]){
          res++;
        }else{
          break;
        }
      }
    }
  }

  return res;
};

• 方法三： 排序加双指针

 var triangleNumber = function (array) {
  const n = array.length;
  array.sort((a, b) => a - b);
  let count = 0;
  for (let i = 0; i < n; ++i) {
      let k = i;
      for (let j = i + 1; j < n; ++j) {
          while (k + 1 < n && array[k + 1] < array[i] + array[j]) {
              ++k;
          }
          count += Math.max(k - j, 0);
      }
  }
  return count;
};